package leetcode.code0110;

import leetcode.helper.HelpDebug;
import leetcode.helper.tree.TreeArray;
import leetcode.helper.tree.TreeNode;

public class Solution110 {

	public boolean isBalanced(TreeNode root) {
		if (root == null)
			return true;
		int left = this.h(root.left);
		int right = this.h(root.right);
		if ((Math.abs(right - left) > 1) || !this.isBalanced(root.left) || !this.isBalanced(root.right))
			return false;
		return true;
	}

	public int h(TreeNode root) {
		if (root == null) {
			return 0;
		}
		int left = this.h(root.left);
		int right = this.h(root.right);
		return Math.max(left, right) + 1;
	}

	public static void main(String[] args) {
		Solution110 so = new Solution110();
		String str = "[3,9,20,null,null,15,7]";
		boolean r = so.isBalanced(TreeArray.array2tree(HelpDebug.str2array4(str)));
		System.out.println(r);
	}

}
